'''
搜索算法
'''
# 1.搜索最小值
def indexOfMin(lyst):
    """return the index of the minimun item"""
    minIndex = 0
    currentIndex = 1
    while currentIndex < len(lyst):
        if lyst[currentIndex] < lyst(minIndex):
            minIndex = currentIndex
        currentIndex += 1
    return minIndex

# 2.顺序搜索一个列表
def sequentialSearch(target, lyst):
    position = 0
    while position < len(lyst):
        if target == lyst[position]:
            return position
        position += 1
    return -1

# 3.二叉搜索
def binarySearch(target, sortedLyst):
    left = 0
    right = len(sortedLyst) - 1
    count = 0
    while left <= right:
        count += 1
        print('当前轮次:%d\nleft:%d, right:%d' % (count, sortedLyst[left], sortedLyst[right]))
        midpoint = (left + right) // 2
        if target == sortedLyst[midpoint]:
            return midpoint
        elif target < sortedLyst[midpoint]:
            right = midpoint - 1
        else:
            left = midpoint + 1
    return -1

# 4.比较数据项（对象）——富方法
class SavingAccount():
    def __init__(self, name, pin, balance=0.0) -> None:
        self._name = name
        self._pin = pin
        self._balance = balance

    def __lt__(self, other):
        return self._name < other._name
    # Other methods, including __eq__

# 练习3.3
# 1）
# pyst = [20, 44, 48, 55, 62, 66, 74, 88, 93, 99]
# a = binarySearch(90, pyst)

'''
基本排序算法
'''
def swap(lyst, i, j):
    temp = lyst[i]
    lyst[i] = lyst[j]
    lyst[j] = temp

# 1.选择排序
def selectionSort1(lyst):
    i = 0
    while i < len(lyst) - 1:
        minIndex = i
        j = i + 1
        while j < len(lyst):
            if lyst[j] < lyst[minIndex]:
                minIndex = j
            j += 1
        if minIndex != i:
            swap(lyst, minIndex, i)
        i += 1

def selectionSort2(lyst):
    for i in range(len(lyst) - 1):
        minIndex = i
        for j in range(i + 1, len(lyst)):
            if lyst[j] < lyst[minIndex]:
                minIndex = j
        if minIndex != i:
            lyst[minIndex], lyst[i] = lyst[i], lyst[minIndex]

# 2.冒泡排序
def bubbleSort1(lyst):
    i = 0   # 第几轮
    n = len(lyst)
    while i < len(lyst) - 1:
        j = 0   # 第几次比较
        while j < n - 1:
            if lyst[j] > lyst[j+1]:
                swap(lyst, j, j+1)
            j += 1
        n -= 1
        i += 1
    return lyst

def bubbleSort2(lyst):
    n = len(lyst)
    while n > 1:    # do n - 1 bubbles
        i = 1
        while i < n:
            if lyst[i] < lyst[i-1]:
                swap(lyst, i, i-1)
            i += 1
        n -= 1

def bubbleSort3(lyst):
    n = len(lyst)
    while n > 1:
        swapped = False
        i = 1
        while i < n:
            if lyst[i] < lyst[i-1]:
                swap(lyst, i, i-1)
                swapped = True
            i += 1
        if not swapped:
            return
        n -= 1

def bubbleSort4(lyst):
    for i in range(len(lyst) - 1):
        exchange = False
        for j in range(len(lyst) - i - 1):
            if lyst[j] > lyst[j+1]:
                lyst[j], lyst[j+1] = lyst[j+1], lyst[j]
                exchange = True
        if not exchange:
            return
# 3.插入排序
def insertSort1(lyst):
    i = 1
    while i < len(lyst):
        itemToInsert = lyst[i]
        j = i - 1
        while j >= 0:
            if itemToInsert < lyst[j]:
                lyst[j + 1] = lyst[j]
                j -= 1
            else:
                break
        lyst[j + 1] = itemToInsert
        i += 1

def insertSort2(lyst):
    for i in range(1, len(lyst)):   # i表示摸到的牌的下标
        tmp = lyst[i]
        j = i - 1   # j表示手里的牌的下标
        while j >= 0 and lyst[j] > tmp:
            lyst[j+1] = lyst[j]
            j -= 1
        lyst[j+1] = tmp

# 4.快速排序-1
def partition(lyst, left, right):
    tmp = lyst[left]
    while left < right:
        while left < right and lyst[right] >= tmp: # 从右边找比tmp小的
            right -= 1  # 往左找一步
        lyst[left] = lyst[right]
        left += 1
        while left < right and lyst[left] <= tmp:   # 从左边找比tmp大的
            left += 1
        lyst[right] = lyst[left]
        right -= 1
    lyst[left] = tmp
    return left # 返回中间元素索引

def _quick_sort(lyst, left, right):
    if left < right:    # 至少存在两个元素
        mid = partition(lyst, left, right)
        _quick_sort(lyst, left, mid-1)
        _quick_sort(lyst, mid+1, right)

def quick_sort(lyst):
    _quick_sort(lyst, 0, len(lyst)-1)


# 4.快速排序-2
